package 力扣日常刷题.木22一月.第05天0112;

import 力扣日常刷题.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/1/12
 * @description
 */
public class Demo02回溯中等不同的二叉搜索树2 {



    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return generateTrees(1, n);
    }

    public List<TreeNode> generateTrees(int start, int end){
        List<TreeNode> allTrees = new LinkedList<TreeNode>();
        if(start > end){
            allTrees.add(null);
            return allTrees;
        }

        // 枚举可行根节点
        for (int i = start; i <= end ; i++) {
            // 获得所有可行的左/右子树集合
            List<TreeNode> leftNode = generateTrees(start,i-1);
            List<TreeNode> rightNode = generateTrees(i+1,end);

            // 为当前根节点生成子树
            for (TreeNode l : leftNode) {
                for (TreeNode r : rightNode) {
                    TreeNode currentTree = new TreeNode(i);
                    currentTree.right = r;
                    currentTree.left = l;
                    allTrees.add(currentTree);
                }
            }
        }
        return allTrees;

    }





}
